package leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-25 19:32
 **/
public class LeetCode107 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //存储总的遍历结果
        List<List<Integer>> list = new ArrayList<>();
        //root为空直接返回
        if (root == null) {
            return list;
        }
        //使用LinkedList作为队列的结构
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        //存储每一层的元素
        List<Integer> list2 = null;
        while (!deque.isEmpty()) {
            //获取当前层元素个数
            int size = deque.size();
            //实例化list2
            list2 = new ArrayList<>();
            //将一层元素值放到list2中
            while (size > 0) {
                TreeNode node = deque.poll();
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
                list2.add(node.val);
                size--;
            }
            //每次都将新的一层的元素查到列表的头部
            list.add(0, list2);
        }

        return list;
    }

}
